package sol.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Triangle
 */
public class Issue120 {
    public int minimumTotal(List<List<Integer>> triangle) {

        int size = triangle.size();
        int[] rowMin = new int[size];

        for (int i = triangle.size() - 1; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                int val = triangle.get(i).get(j);
                if (i == triangle.size() - 1)
                    rowMin[j] = val;
                else {
                    rowMin[j] = val + Math.min(rowMin[j], rowMin[j + 1]);
                }
            }
        }

        return rowMin[0];
    }


    public static void main(String[] args) {
        final List<Integer> row1 = new ArrayList<Integer>() {{
            add(2);
        }};
        final List<Integer> row2 = new ArrayList<Integer>() {{
            add(3);
            add(4);
        }};
        final List<Integer> row3 = new ArrayList<Integer>() {{
            add(6);
            add(5);
            add(7);
        }};
        final List<Integer> row4 = new ArrayList<Integer>() {{
            add(4);
            add(1);
            add(8);
            add(3);
        }};
        List<List<Integer>> triangle = new ArrayList<List<Integer>>() {{
            add(row1);
            add(row2);
            add(row3);
            add(row4);
        }};

        Issue120 sol = new Issue120();
        System.out.println(sol.minimumTotal(triangle));
    }
}
